#include<stdio.h>
#include<stdlib.h>

typedef struct ListNode
{
    int val;
    struct ListNode* next;
}ListNode;
ListNode* partition(ListNode* pHead, int x)
{
    ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
    ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
    phead->next = pHead;
    ListNode* tail = guard;
    ListNode* perv = phead;
    ListNode* cur = phead->next;

    while (cur)
    {
        if (cur->val < x)
        {
            perv->next = cur->next;
            tail->next = cur;
            tail = tail->next;
            tail->next = NULL;
            cur = perv->next;
        }
        else
        {
            perv = cur;
            cur = cur->next;
        }
    }
    tail->next = phead->next;
    return guard->next;
}